class Array(object):
    """
    定义一个数组
    数组里面放 Slot
    """
    def __init__(self, size=32, default=None):
        self.size = size
        self.items = [default] * size

    def __getitem__(self, index):
        return self.items[index]

    def __setitem__(self, index, value):
        self.items[index] = value

    def __len__(self):
        return self.size

    def clear(self, default=None):
        for i in range(len(self.items)):
            self.items[i] = default

    def __iter__(self):
        for item in self.items:
            yield item


class Slot(object):
    """
    定义一个hash表数组槽(slot这里指的就是数组的一个位置)
    hash table就是一个数组,每个数组的元素(slot 槽)是一个对象,对象包含两个属性key和value

    注意,一个槽有三种状态,看你能否想明白.相比链接发解决冲突,探查法删除一个key的操作稍微复杂.
    1. 从未使用HashMap: UNUSED, 此槽没有被使用和冲突过,查找时只要找到 UNUSED 就不再继续探查了
    2. 使用过但是 remove了: EMPTY 该探查点后边的元素任然可能是有key的,需要继续查找
    3. 槽正在被使用
    """
    def __init__(self, key, value):
        self.key, self.value = key, value


class HashTable(object):
    UNUSED = None  # 没被使用过
    EMPTY = Slot(None, None)  # 使用却被删除过

    def __init__(self):
        self.table = Array(8, default=HashTable.UNUSED)  # 保持 2 * i 次方
        self.length = 0  # HashTable 的长度也就是 Array 的长度,这里的长度不包含 EMPTY 的槽位

    def __len__(self):
        return self.length

    # in operator, 实现之后可以使用 in 操作符判断
    def __contains__(self, item):
        index = self.find_key(item)
        return index is not None

    @property
    def load_factor(self):
        return self.length / float(len(self.table))  # load_factor 超过 0.8 重新分配

    # 进行哈希
    def hash(self, key):
        return abs(hash(key)) % len(self.table)

    # 查找key
    def find_key(self, key):
        """
        解释一个 slot 为 UNUSED 和 EMPTY 的区别
        因为使用的是二次探查的方法,假如有两个元素 A, B 冲突了
        首先 A hash 得到的是 slot 下标 5, A 放到了第5个槽, 之后插入 B 因为冲突,所以继续根据二次探查方式放到了 slot 下标8.
        然后删除 A, 槽 5 被置为 EMPTY.
        然后去查找 B,第一次 hash 得到的是槽 5, 但是这个时候我还是需要二次计算 hash 才能找到 B
        但是如果槽式 UNUSED 就不用继续找了, 认为 B 就是不存在的元素.
        这个就是 UNUSED 和 EMPTY 的区别.
        """
        origin_index = index = self.hash(key)  # origin_index 判断是否又走到了起点,如果查找了一圈都找不到则无此元素
        _len = len(self.table)  # 已使用和 EMPTY 的值
        while self.table[index] is not HashTable.UNUSED:
            # if self.table[index] is HashTable.EMPTY:  # 继续寻找
            #     index = (index * 5 + 1) % _len
            #     if index == origin_index:
            #         break
            #     continue
            if self.table[index].key == key:  # 找到了key
                return index
            # else:
            index = (index * 5 + 1) % _len
            if index == origin_index:
                break
        return None  # 没有找到

    # 找到能插入的槽
    def find_slot_for_insert(self, key):
        index = self.hash(key)
        _len = len(self.table)
        while not self.slot_can_insert(index):
            index = (index * 5 + 1) % _len
        return index

    # 槽是否能被插入
    def slot_can_insert(self, index):
        return self.table[index] in [HashTable.EMPTY, HashTable.UNUSED]

    # 添加元素
    def add(self, key, value):
        if key in self:  # update
            index = self.find_key(key)
            self.table[index].value = value
            return False
        else:  # 新增
            index = self.find_slot_for_insert(key)
            self.table[index] = Slot(key, value)
            self.length += 1
            if self.load_factor >= 0.8:
                self.rehash()

            return True

    # 槽不够时,分配新的存储空间,重哈希
    def rehash(self):
        old_table = self.table
        new_size = len(self.table) * 2
        self.table = Array(new_size, HashTable.UNUSED)
        self.length = 0

        for slot in old_table:
            if slot not in [HashTable.UNUSED, HashTable.EMPTY]:
                index = self.find_slot_for_insert(slot.key)
                self.table[index] = slot
                self.length += 1

    # 获取值
    def get(self, key, default="not find"):
        index = self.find_key(key)
        if index:
            return self.table[index].value
        return default

    # 移除
    def remove(self, key):
        index = self.find_key(key)
        if index is None:
            raise KeyError()
        value = self.table[index].value
        self.length -= 1
        self.table[index] = HashTable.EMPTY
        return value

    # 遍历
    def __iter__(self):
        for slot in self.table:
            if slot not in (HashTable.EMPTY, HashTable.UNUSED):
                yield f"{slot.key} {slot.value}"


if __name__ == '__main__':
    import string
    h = HashTable()
    # keys = string.ascii_letters
    # for index, key in enumerate(keys):
    #     h.add(key, index)
    h.add('a', 0)
    print(6, sorted(list(h)))  # ['b', 'c']
    h.add('b', 1)
    print(6, sorted(list(h)))  # ['b', 'c']
    h.add('c', 2)
    print(6, sorted(list(h)))  # ['b', 'c']
    print(1,len(h))  # 3
    print(2,h.get('a'))  # 0
    print(3,h.get('b'))  # 1
    print(4,h.get('hehe'))  # None
    h.remove('a')
    print(5,h.get('a'))  # None
    print(6,sorted(list(h)))  # ['b', 'c']
    for hh in h:
        print(hh)